/*
https://leetcode-cn.com/problems/cheapest-flights-within-k-stops/solution/k-zhan-zhong-zhuan-nei-zui-bian-yi-de-ha-abzi/
 */

public class Solution787 {
    private static final int MAX = 2147483647/3;

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int[][] dis=new int[105][105];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dis[i][j]=MAX;
            }
        }
        dis[0][src]=0;

        for (int[] flight:flights){
            if (flight[0]==src){
                dis[0][flight[1]]=flight[2];
            }
        }

        for (int i = 0; i < k ; i++) {
            for (int j = 0; j < n; j++) {
                dis[i+1][j]=dis[i][j];
            }
            for (int[] flight:flights){
                if (dis[i][flight[0]]+flight[2]<dis[i+1][flight[1]]){
                    dis[i+1][flight[1]]=dis[i][flight[0]]+flight[2];
                }
            }
        }
        return (dis[k][dst]==MAX)?-1:dis[k][dst];
    }

    public static void main(String[] args) {
        System.out.println(new Solution787().findCheapestPrice(3,new int[][]{{0,1,100},{1,2,100},{0,2,500}},0,2,1));
    }
}
